#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//最长定差子序列
//https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/
//class Solution {
//public:
//    int longestSubsequence(vector<int>& arr, int difference) {
//        int n = arr.size();
//
//        unordered_map<int, int> m;
//        m[arr[0]] = 1;
//        //m[arr[i]] 表示值为arr[i] 时的这个值的最大子序列
//        int ret = 1;
//        //当arr中有多个重复值时，我们只需要离arr[i]最近的那个即可 所以重复的值遍历到后面时可以一直更新为最长的那个值
//        for (int i = 1; i < n; ++i)
//        {
//            m[arr[i]] = m[arr[i] - difference] + 1; //如果这个值不存在则会被插入且值为0
//            ret = max(ret, m[arr[i]]);
//        }
//        return ret;
//    }
//};


//最长的斐波那契子序列的长度
//https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/description/
// class Solution {
// public:
//     int lenLongestFibSubseq(vector<int>& arr) {
//         int n = arr.size();
//         //因为是严格递增的所以没有重复值

//         unordered_map<int,int> m; //优化下标查询
//         for(int i = 0;i<n;++i) m[arr[i]] = i; //存储arr值与其下标关系 做到O(1)查询
//         //对于i，j的计算 我们不看ij以外的其他值 ij记录了他们所能组成的最大值
//         vector<vector<int>> vv(n,vector<int>(n,2)); //n*n的数组表示第i和第j个数合起来可以表示当前位置的数 满足斐波那契条件
//         //初始化为2是因为斐波那契最低就是3个数 方便后面的数计算
//         //n*n表示该数可以与表中数组成的每种可能

//         //1 2 3
//     //  num j i
//         //arr = arr[i]+arr[j] 且j<i k下标的值不能在j前面 保证严格递增
//         int ret = 2; //ret默认为2
//         for(int i = 2;i<n;++i) //arr值
//         {
//             for(int j = 1;j<i;++j) //离arr数的倒数第一个值 至少是下标1处 如果是下标0处不能组成斐波那契数
//             {
//                 //开始更新
//                 int num = arr[i]-arr[j]; //两数相减得到第三个斐波那契数应该的值
//                 //如果求出的值小于i位置的值且在hash表中存在则更新表v[i][j]
//                 if(num < arr[j] && m.count(num)) vv[j][i] = vv[m[num]][j]+1; //表示num值的下标和i下标两个下标所对应的值组成的斐波那契数列的最大长度
//                 ret = max(ret,vv[j][i]);
//             }
//         }
//         return ret<3?0:ret; //如果ret<3则表示没有可以组成的斐波那契数
//     }
// };


//1027. 最长等差数列
//https://leetcode.cn/problems/longest-arithmetic-subsequence/description/
// class Solution {
// public:
//     int longestArithSeqLength(vector<int>& nums) {
//         int n = nums.size();

//         //每一个等差数列长度至少是2，然后跟一个数凑成3 所以等差数列的起步是2
//         //1 2 3
//         //a b c
//         //我们从b开始，联合b c 通过公式 a = 2b-c 推出a 并求出这个数的下标 所以需要一个哈希表存储数与下标的映射关系
//         //因为里面可能存在重复值 所以我们只需要存储当前离b位置 最近的一个重复值与其映射的下标即可
//         vector<vector<int>> vv(n,vector(n,2));
//         unordered_map<int,int> m; //下标映射
//         m[nums[0]] = 0; //先存储0号位置元素下标
//         int ret = 2;
//         //我们两个元素一起推敲第三个元素 推断每一个两元素组合的最大等差数列
//         //先确定b下标可以保证我们方便保存离我们最近的那个元素的下标
//         //如果确定c再确定b则a的下标不好确定 因为我们需要保存a最近的一个下标
//         for(int i = 1;i<n;++i) //确定b下标
//         {
//             for(int k = i+1;k<n;++k) //确定c下标
//             {
//                 int num = 2*nums[i]-nums[k]; //根据公式a=2b-c 求出a
//                 //此处推断是m[num] i k 能否组成等差数列
//                 if(m.count(num)) vv[i][k] = vv[m[num]][i] + 1; //i k的最长元素数等于m[num]i处的最大元素下标+1
//                 ret = max(ret,vv[i][k]);
//             }
//             //每次遍历完成后 将b的下标保存(保存最近的一个下标)
//             m[nums[i]] = i;
//         }
//         return ret;
//     }
// };